//
// Created by summerday on 2021/6/3.
//

#include <cstdio>
#include<iostream>

using namespace std;
typedef struct LNode {
    int data; // 数据域
    struct LNode *next; // 指针域
} LNode, *LinkList;

bool insertNextNode(LNode *p, int e);

LNode *getElem(LinkList list, int i);


bool initList(LinkList &list) {
    list = (LNode *) malloc(sizeof(LNode *));
    if (list == nullptr) return false;
    list->next = nullptr;
    return true;
}

// 头插法
LinkList List_HeadInsert(LinkList &list) {
    LNode *s;
    int x;
    list = (LNode *) malloc(sizeof(LNode *));
    list->next = NULL;
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *) malloc(sizeof(LNode *));
        s->data = x;
        s->next = list->next;
        list->next = s;
        scanf("%d", &x);
    }
    return list;
}

// 尾插法
LinkList list_TailInsert(LinkList &list) {
    int x;
    list = (LinkList) malloc(sizeof(LNode));
    // r 为尾指针
    LNode *s, *r = list;
    scanf("%d", &x);

    while (x != 9999) {
        s = (LNode *) malloc(sizeof(LNode *));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = nullptr;
    return list;
}


// 序号查找结点
LNode *getElem(LinkList list, int i) {
    int j = 1;
    LNode *p = list->next;
    if (i == 0) return list;
    if (i < 1) return nullptr;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

// 删除i位置的结点
bool listDelete(LinkList &list, int i) {
    if (i < 1) return false;
    LNode *p, *q;
    p = getElem(list, i - 1);
    q = p->next;
    p->next = q->next;
    free(q);
    return true;
}

// 删除指定结点
bool deleteNode(LNode *p) {
    if (p == nullptr) return false;
    LNode *q;
    q = p->next; // 如果p为最后一个结点，会bug
    p->data = q->data;
    p->next = q->next;
    free(q);
    return true;
}

// 按值查找
LNode *getByValue(LinkList list, int val) {
    LNode *p = list->next;
    while (p != NULL && p->data != val) {
        p = p->next;
    }
    return p;
}

// 在第i个位置插
bool listInsert(LinkList &list, int i, int e) {
    if (i < 1) return false;
    LNode *p = getElem(list, i - 1);
    return insertNextNode(p, e);
}

// 前插 1 找到前驱(o(n))， 2 偷天幻日o(1)
bool insertPrevNode(LNode *p, int e) {
    if (p == nullptr) return false;
    LNode *s = (LNode *) malloc(sizeof(LNode));
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}

// 后插
bool insertNextNode(LNode *p, int e) {
    if (p == nullptr) return false;
    LNode *s = (LNode *) malloc(sizeof(LNode));
    if (s == nullptr) return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

int len(LinkList list) {
    int s = 0;
    for (LNode *p = list->next; p; p = p->next, s++);
    return s;
}

void print(LinkList list) {
    for (LNode *p = list->next; p; p = p->next) {
        cout << p->data << " ";
    }
    cout << endl;
}

// --------- ----- ------ ----- -------- ------------

// 递归删除不带头结点的单链表 值为 val元素
void test_1(LinkList &list, int val) {
    LNode *p;
    // 递归终止条件
    if (list == NULL) return;
    // 当前为val
    if (list->data == val) {
        p = list;
        list = list->next;
        free(p);
        test_1(list, val);
        // 当前不为val
    } else {
        test_1(list->next, val);
    }

}

/**
 * test_2 在带头结点的单链表list 中，删除所有值为 x的结点。并释放其空间，假设值为x的结点不唯一，试编写算法以实现上述操作。
 * @param list
 */
void test_2_1(LinkList &list, int x){
    LNode  *pre = list, *cur = list->next, *p;
    while(cur != NULL){
        if(cur->data == x){
            p = cur;
            cur = cur->next;
            pre->next = cur;
            free(p);
            continue;
        }else{
            cur = cur->next;
            pre = pre->next;
        }
    }
}
// 尾插法建立新的链表
void test_2_2(LinkList &list, int x){

    LNode *p = list->next, *r = list, *q;
    while(p!= NULL) {
        if (p->data != x) {
            r->next = p;
            r = p;
            p = p->next;
        } else {
            q = p;
            p = p->next;
            free(q);
        }
    }
    r->next = NULL;
}

/**
 * 为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。
 * @param list
 */
void test_3_reverse_print(LinkList list){
    if(list->next != NULL){
        test_3_reverse_print(list->next);
    }
    if(list != NULL)
        printf("%d ", list->data);
}

/**
 * 试编写在带头结点的单链表L 中删除一个最小值结点的高效算法（假设最小值结点是唯一的）。
 * @param list
 */
void test_4_find_min(LinkList &head){
    LNode *pre = head, *p = head->next;
    LNode *minPre = pre, *min = p;
    while(p != NULL){
        if(min->data < p->data){
            minPre = pre;
            min = p;
        }
        pre = p;
        p = p->next;
    }
    minPre->next = min->next;
    free(min);
}

/**
 * 带头结点单链表就地逆置
 * @param head
 */
LinkList test_5_reverse(LinkList &head){
    LNode *pre = NULL, *cur, *next;
    cur = head->next;
    while(cur != NULL){
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    head->next = pre;
    return head;
}

/**
 * 带头结点 递增有序
 * @param head
 * @return
 */
LinkList test_6_sort_asc(LinkList &head){
    LNode *p = head->next, *pre;
    LNode *r = p->next;

    // 构造只含一个数据的有序表
    p->next = nullptr;
    p = r;

    while(p){
        r = p->next;
        pre = head;
        // 一直找到最后一个小于它的数
        while(pre ->next != NULL && pre->next->data < p->data){
            pre = pre->next;
        }
        p->next = pre->next;
        pre->next = p;
        p = r;
    }
    return head;
}

void infoShow(LinkList list) {
    cout << "------ info show ------" << endl;
    cout << "length : " << len(list) << endl;
    print(list);
}

//int main() {
//    LinkList list;
//    list_TailInsert(list);
//
//    infoShow(list);
//
//    LinkList head = test_6_sort_asc(list);
//
//    infoShow(head);
//
//    return 0;
//
//}